/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Apr 21, 2014
 */
package zhoujian.oj.leetcode;

import java.util.Stack;

import org.junit.Test;

/**
 * @version 1.0
 * @description Evaluate the value of an arithmetic expression in Reverse Polish
 *              Notation.
 * 
 *              Valid operators are +, -, *, /. Each operand may be an integer
 *              or another expression.
 * 
 *              Some examples: ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
 *              ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
 */
public class EvaluateReversePolishNotation {

	public int evalRPN(String[] tokens) {
		Stack<Integer> stack = new Stack<>();
		int op1;
		int op2;
		for (int i = 0; i < tokens.length; i++) {
			switch(tokens[i]) {
			case "+":
				op1 = stack.pop();
				op2 = stack.pop();
				stack.push(op2 + op1);
				break;
			case "-":
				op1 = stack.pop();
				op2 = stack.pop();
				stack.push(op2 - op1);
				break;
			case "*":
				op1 = stack.pop();
				op2 = stack.pop();
				stack.push(op2 * op1);
				break;
			case "/":
				op1 = stack.pop();
				op2 = stack.pop();
				stack.push(op2 / op1);
				break;
			default:
				stack.push(Integer.valueOf(tokens[i]));
			}
		}
		return stack.pop();
	}
	
	@Test
	public void testEvalRPN() {
		String[] tokens = new String[] {"4", "13", "5", "/", "+"};
		System.out.println(evalRPN(tokens));
	}
	
}
